맨위로가기

상호 배제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

상호 배제는 여러 프로세스가 공유 자원에 동시에 접근하는 것을 제어하는 문제로, 임계 구역 내에서 한 번에 하나의 프로세스만 자원을 사용할 수 있도록 하는 해결책을 제시한다. 이러한 해결책은 교착 상태가 없고, 락아웃 프리 또는 k-바운디드 대기 속성을 가져야 한다. 상호 배제는 하드웨어적, 소프트웨어적 방법으로 구현될 수 있으며, 하드웨어적 방법에는 인터럽트 비활성화, 바쁜 대기, 비교-교환 등이 있다. 소프트웨어적으로는 데커, 피터슨, 빵집 알고리즘 등이 사용되며, 고급 상호 배제 기법으로는 락, 세마포어, 모니터 등이 있다. 주의해야 할 현상으로는 기아 상태, 교착 상태, 콘보이 현상 등이 있다.

더 읽어볼만한 페이지

  • 자료 구조 - 라우팅 테이블
    라우팅 테이블은 네트워크에서 데이터 전송 시 최적 경로를 결정하는 핵심 데이터베이스로, 라우터가 목적지 IP 주소를 기반으로 다음 홉을 결정하며 직접 연결 및 원격 네트워크 경로 정보를 저장하고 동적 라우팅 또는 수동 설정으로 관리된다.
  • 자료 구조 - 스택
    스택은 후입선출(LIFO) 원칙에 따라 데이터를 관리하는 추상 자료형으로, push 연산으로 데이터를 쌓고 pop 연산으로 가장 최근 데이터를 제거하며, 서브루틴 호출 관리, 수식 평가, 백트래킹 등에 활용된다.
  • 에츠허르 데이크스트라 - 교착 상태
    교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다.
  • 에츠허르 데이크스트라 - 세마포어
    세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다.
  • 동시성 제어 - 세마포어
    세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다.
  • 동시성 제어 - 모니터 (동기화)
    모니터는 공유 자원 접근을 제어하여 프로세스 간 동기화를 구현하는 프로그래밍 구조로, 뮤텍스 락, 조건 변수 등으로 구성되어 경쟁 상태를 방지하며 여러 프로그래밍 언어에서 지원된다.
상호 배제
상호 배제
컴퓨팅
종류동기화 메커니즘
용도경쟁 조건을 방지하고 임계 구역에서 데이터 일관성을 유지
관련 개념교착 상태
세마포어
뮤텍스
모니터
읽기-쓰기 잠금
스핀 잠금
재진입 가능
원자성
구현 방법
소프트웨어데커 알고리즘
피터슨 알고리즘
램포트의 빵집 알고리즘
하드웨어테스트 앤 셋

2. 문제 정의

상호 배제는 여러 프로세스가 공유 자원에 동시에 접근할 때 발생할 수 있는 문제를 해결하기 위한 것으로, 자원 공유 문제를 다룬다. 즉, 각 프로세스가 작업을 수행하는 동안 해당 자원에 대한 배타적인 제어가 필요할 때, 소프트웨어 시스템이 어떻게 여러 프로세스의 공유 자원 접근을 제어할 수 있는가? 하는 문제이다. 상호 배제는 프로세스가 임계 구역이라는 특정 코드 세그먼트에 있을 때만 공유 자원을 사용할 수 있도록 한다. 이는 자원을 사용할 프로그램의 해당 부분에 대한 각 상호 실행을 제어함으로써 공유 자원에 대한 접근을 제어하는 방식이다.

성공적인 상호 배제 솔루션은 최소한 다음 두 가지 속성을 만족해야 한다.


  • '''상호 배제''': 한 번에 하나의 프로세스만 임계 구역에 있을 수 있다.
  • '''교착 상태 방지''': 프로세스가 임계 구역에 진입하려 할 때, 영구적으로 임계 구역에 남아 있지 않는 한, 결국에는 그중 하나가 성공적으로 진입해야 한다.

2. 1. 교착 상태와 기아 상태

교착 상태는 상호 배제에 의해 잠긴 자원에 대해 다른 사용자로부터 접근 요청이 있을 때, 양쪽 모두 서로 사용 중인 자원이 해제되기를 기다리며 블록 상태가 되는 상황을 말한다. 둘 이상의 사용자 간에 발생하며, 이 상태에서는 어떤 사용자도 자원 해제를 기다리며 처리가 진행되지 않고 정지 상태가 된다.[4]

기아 상태는 두 프로세스가 지속적으로 자원을 서로 주고받는 경우, 세 번째 프로세스가 락아웃되어 시스템이 교착 상태에 있지 않더라도 자원 기아를 경험할 수 있는 상황을 말한다. 시스템이 락아웃으로부터 자유로우면 모든 프로세스가 미래의 어느 시점에서 차례를 얻을 수 있도록 보장한다.[4]

  • '''락아웃 프리'''는 임계 구역에 진입하려는 모든 프로세스가 결국 그렇게 할 수 있도록 보장한다. 이는 교착 상태 회피와는 구별되는데, 어떤 대기 프로세스가 임계 구역에 접근할 수 있어야 하지만 모든 프로세스가 차례를 얻을 필요는 없다는 것을 요구한다.
  • '''k-바운디드 대기 속성'''은 락아웃 프리보다 더 정확한 약속을 제공한다. 락아웃 프리는 모든 프로세스가 결국 임계 구역에 접근할 수 있도록 보장하지만, 대기 시간이 얼마나 걸릴지에 대해서는 보장하지 않는다. ''k''-바운디드 대기 속성에서 각 프로세스는 유한한 최대 대기 시간을 갖는다. 이는 다른 프로세스가 대기열을 끊을 수 있는 횟수를 제한하여 다른 프로세스가 대기하는 동안 하나의 프로세스가 임계 구역에 ''k''번 이상 들어갈 수 없도록 하는 방식으로 작동한다.[4]

2. 2. 프로세스 상태

프로세스의 실행 단계는 비임계 구역, 시도, 임계 구역, 종료의 네 가지 상태로 나눌 수 있다. 프로그램 실행은 다음 순서로 이 네 가지 상태를 순환한다.[5]

단일 프로세스의 섹션 주기

  • 비임계 구역: 임계 구역 외부에 있는 작업이다. 프로세스는 공유 자원을 사용하거나 요청하지 않는다.

  • 시도: 프로세스가 임계 구역에 진입을 시도한다.

  • 임계 구역: 프로세스가 이 섹션에서 공유 자원에 접근할 수 있다.

  • 종료: 프로세스가 임계 구역을 종료하고 공유 자원을 다른 프로세스에서 사용할 수 있도록 한다.


프로세스가 임계 구역에 진입하려는 경우, 먼저 시도 섹션을 실행하고 임계 구역에 접근할 때까지 기다려야 한다. 프로세스가 임계 구역을 실행하고 공유 자원 사용을 마친 후에는 종료 섹션을 실행하여 다른 프로세스에서 사용할 수 있도록 해제해야 한다. 그런 다음 프로세스는 비임계 구역으로 돌아간다.[5]

3. 상호 배제 구현 방법

상호 배제를 구현하는 방법에는 하드웨어적인 방법과 소프트웨어적인 방법이 있다.

하드웨어적 해결책으로는 단일 프로세서 시스템에서 인터럽트를 비활성화하는 방법, 바쁜 대기를 활용하는 방법, 원자적 테스트 앤 셋 명령어, 비교-교환(CAS) 등이 있다.

소프트웨어적 해결책으로는 데커 알고리즘, 피터슨 알고리즘, 램포트의 빵집 알고리즘[13], 시만스키 알고리즘, 타우벤펠트의 흑백 빵집 알고리즘[12], 마에카와 알고리즘 등이 있다. 이들은 바쁜 대기를 활용하여 상호 배제를 구현한다. 그러나 이러한 알고리즘은 아웃 오브 오더 실행이 이루어지는 플랫폼에서는 제대로 작동하지 않을 수 있으므로, 메모리 배리어를 구현하는 기계어 명령을 가진 CPU 플랫폼을 활용해야 한다.[14]

대부분의 경우 운영 체제의 멀티스레딩 라이브러리가 제공하는 동기화 기능을 사용하는 것이 더 효율적이다. 이러한 기능은 하드웨어 솔루션을 활용하거나, 하드웨어 솔루션이 없는 경우 소프트웨어 솔루션을 사용한다. 예를 들어, 운영 체제의 락 라이브러리를 사용할 때, 스레드가 이미 획득된 락을 획득하려고 시도하면, 운영 체제는 컨텍스트 스위치를 통해 해당 스레드를 일시 중단시키고 실행 가능한 다른 스레드로 교체한다. 실행 가능한 다른 스레드가 없다면 프로세서를 저전력 상태로 전환하여 에너지 소비를 줄인다.

현대적인 상호 배제 방법은 큐잉과 컨텍스트 스위칭을 통해 지연 시간과 바쁜 대기를 최소화한다. 하지만 스레드를 일시 중단하고 다시 복원하는 데 시간이 오래 걸리는 특정 상황에서는 스핀락이 더 적합할 수 있다.

3. 1. 하드웨어적 해결책

단일 프로세서 시스템에서 상호 배제를 달성하는 가장 간단한 방법은 프로세스가 임계 구역에 있는 동안 인터럽트를 비활성화하는 것이다. 이렇게 하면 인터럽트 서비스 루틴이 실행되지 않아 프로세스가 선점되지 않는다. 이 방법은 효과적이지만, 임계 구역이 길어지면 시스템 시계가 느려지거나, 프로세스가 임계 구역 내에서 멈출 경우 시스템 전체가 멈추는 문제가 발생할 수 있다.

바쁜 대기는 단일 프로세서 및 멀티 프로세서 시스템 모두에서 상호 배제를 구현하는 데 효과적이다. 공유 메모리와 원자적 테스트 앤 셋 명령어를 사용하면 한 번에 하나의 프로세스만 플래그를 설정할 수 있다. 플래그 설정에 실패한 프로세스는 다른 작업을 수행하거나, 다른 프로세스에 프로세서를 양보하거나, 성공할 때까지 루프를 반복할 수 있다. 이 방식은 프로세스가 잠금을 보유한 채 멈추더라도 시스템은 계속 작동하도록 한다.

비교-교환(CAS)은 데이터 구조의 상호 배제를 제공하는 또 다른 원자적 연산이다. CAS를 사용하면 각 노드가 수행할 연산을 나타내는 연결 리스트를 생성하여 대기 없는 상호 배제를 달성할 수 있다. 한 번에 하나의 프로세스만 CAS를 통해 연결 리스트에 새 노드를 삽입할 수 있으며, 실패한 프로세스는 다시 시도해야 한다. 각 프로세스는 데이터 구조의 로컬 복사본을 유지하고, 연결 리스트를 탐색하며 각 연산을 로컬 복사본에 적용할 수 있다.

3. 2. 소프트웨어적 해결책

바쁜 대기를 활용하여 하드웨어 지원 없이 소프트웨어만으로 상호 배제를 구현하는 여러 알고리즘이 존재한다. 이러한 알고리즘들은 다음과 같다.

  • 데커 알고리즘
  • 피터슨 알고리즘
  • 램포트의 빵집 알고리즘[13]
  • 시만스키 알고리즘
  • 타우벤펠트의 흑백 빵집 알고리즘[12]
  • 마에카와 알고리즘


하지만, 이러한 알고리즘들은 아웃 오브 오더 실행이 이루어지는 플랫폼에서는 제대로 동작하지 않는다. 알고리즘이 올바르게 작동하려면, 프로그래머는 스레드 내의 메모리 연산 순서를 엄격하게 지정해야 한다.[14] 이를 위해 메모리 배리어를 구현하는 기계어 명령을 가진 CPU 플랫폼을 활용할 수 있다.

대부분의 경우, 운영 체제의 멀티스레딩 라이브러리가 제공하는 동기화 기능을 사용하는 것이 더 효율적이다. 이러한 기능들은 하드웨어 솔루션을 활용하거나, 하드웨어 솔루션이 없는 경우 소프트웨어 솔루션을 사용한다. 예를 들어, 운영 체제의 락 라이브러리를 사용할 때, 스레드가 이미 획득된 락을 획득하려고 시도하면, 운영 체제는 컨텍스트 스위치를 통해 해당 스레드를 일시 중단시키고 실행 가능한 다른 스레드로 교체한다. 만약 실행 가능한 다른 스레드가 없다면, 프로세서를 저전력 상태로 전환하여 에너지 소비를 줄일 수 있다.

이처럼 현대적인 상호 배제 방법들은 큐잉과 컨텍스트 스위칭을 통해 지연 시간과 바쁜 대기를 최소화한다. 그러나 스레드를 일시 중단하고 다시 복원하는 데 걸리는 시간이, 차단된 후 스레드가 실행 준비될 때까지 대기하는 시간보다 길다고 보장할 수 있는 특정 상황에서는 스핀락이 더 적합한 해결책이 될 수 있다.

4. 고급 상호 배제

락(뮤텍스), 읽기-쓰기 락, 재귀 락, 세마포어, 모니터, 메시지 전달, 튜플 공간 등은 고급 동기화 프리미티브이다.[1]

이러한 상호 배제는 부작용을 가질 수 있다. 예를 들어, 고전적인 세마포어는 한 프로세스가 세마포어를 얻고, 다른 프로세스가 두 번째 세마포어를 얻은 다음 둘 다 다른 세마포어가 해제될 때까지 기다리는 교착 상태를 허용한다. 다른 일반적인 부작용으로는 프로세스가 완료될 만큼 충분한 리소스를 얻지 못하는 기아, 우선순위가 높은 스레드가 우선순위가 낮은 스레드를 기다리는 우선 순위 역전, 인터럽트에 대한 응답이 즉각적이지 않은 높은 지연 시간이 있다.[1]

많은 연구는 위와 같은 부작용을 제거하는 데 목표를 두고 있으며, 종종 논블로킹 진행을 보장하는 것을 목표로 한다. 완벽한 방식은 알려져 있지 않다. 블로킹 시스템 호출은 전체 프로세스를 잠들게 했다. 그러한 호출이 스레드 안전해질 때까지, 프로세스 내에서 단일 스레드를 잠들게 하는 적절한 메커니즘은 없었다 (폴링 참조).[1]

5. 주의해야 할 현상과 성질

상호 배제는 여러 프로세스나 스레드가 동시에 공유 자원에 접근할 때 발생할 수 있는 문제를 해결하기 위한 중요한 개념이다. 하지만 상호 배제 구현에는 주의해야 할 여러 현상과 성질이 존재한다.


  • 교착 상태(데드락): 둘 이상의 프로세스나 스레드가 서로 상대방이 점유하고 있는 자원을 기다리면서 무한정 대기하는 상태이다. 예를 들어, 프로세스 1이 자원 A를 점유하고 자원 B를 기다리고, 프로세스 2가 자원 B를 점유하고 자원 A를 기다리는 경우가 해당된다.
  • 기아(Starvation): 특정 프로세스나 스레드가 자원을 얻기 위해 무한정 대기하는 상태이다. 다른 프로세스들이 계속해서 자원을 획득하고 반납하는 동안, 해당 프로세스는 자원을 얻을 기회를 얻지 못한다.
  • 우선 순위 역전: 우선순위가 낮은 프로세스가 자원을 점유하고 있어 우선순위가 높은 프로세스가 해당 자원을 사용하기 위해 대기하는 상태이다. 이로 인해 시스템의 응답성이 저하될 수 있다.
  • 높은 지연 시간: 상호 배제 구현 방식에 따라, 프로세스가 공유 자원에 접근하기까지 오랜 시간이 걸릴 수 있다. 특히 인터럽트 처리와 같이 빠른 응답이 필요한 경우 문제가 될 수 있다.
  • 라이브락(Livelock): 데드락과 유사하지만, 프로세스들이 자원을 얻기 위해 계속해서 시도하지만 서로 양보하는 과정에서 무한 루프에 빠지는 상태이다. 예를 들어, 좁은 길에서 두 사람이 서로 비켜주려다가 같은 방향으로 움직이는 상황이 반복되는 것을 생각할 수 있다.


이러한 문제점을 해결하기 위해 많은 연구가 진행되고 있으며, 논블로킹 진행을 보장하는 알고리즘 개발 등이 이루어지고 있다.

  • 페어니스(Fairness): 공유 자원을 사용하려는 모든 프로세스에게 공평한 기회를 제공해야 한다는 속성이다. 예를 들어, 여러 사람이 매표소에서 줄을 서서 표를 구매할 때, 특정 사람이 계속해서 다른 줄로 옮겨 다니면서 다른 사람들의 기회를 빼앗는 상황을 방지해야 한다.
  • k-바운디드 대기: 특정 프로세스가 자원을 요청한 후, 최대 k번 다른 프로세스에게 자원 사용을 양보하면 반드시 자원을 획득할 수 있도록 보장하는 페어니스의 정도를 측정하는 지표이다.

5. 1. 콘보이 현상

어떤 프로세스가 락을 획득했음에도 불구하고, 해당 프로세스가 실제로 CPU에서 실행되지 않아 실질적으로 어떤 프로세스나 CPU도 임계 구역 내의 처리를 실행하지 않는 상태를 말한다. 이는 락의 목적에 비추어 볼 때 무의미한 상태이다. 락 획득부터 임계 구역 내의 처리를 시작하기까지 지연이 발생하거나 컨텍스트 스위치의 횟수가 증가하기 때문에, 시스템의 응답 지연 증가 및 전체 성능 저하를 초래한다.[15]

락을 해제한 프로세스가 해당 락을 기다리며 슬립하고 있는 프로세스 중 하나에게 락의 소유권을 직접 넘겨주는 구현으로 되어 있을 경우 발생하기 쉬워진다. 대책으로서, 락을 획득하고 싶은 프로세스는 반드시 스스로 락 획득을 시도하는 구현으로 함으로써 문제가 경감된다. 전형적인 예는 스핀락으로, 락을 획득하고 싶은 프로세스는 사양상 결코 슬립하지 않는다. 반대로 락 대기 프로세스가 슬립하는 경우, 슬립 종료부터 락 획득까지의 절차에 따라 콘보이에 빠지기 쉬워진다.[15]

우선순위 상한 프로토콜은 우선순위가 지원되는 환경에서, 우선순위 상속은 락 소유 중인 프로세스보다 우선순위가 높은 프로세스가 락을 획득하려 할 경우, 각각 이 문제를 우선순위에 의존하는 별개의 접근 방식으로 해결하려 한다. 하지만, 콘보이의 본질은 "프로세스가 실제로 CPU에서 실행 중이 아님에도 불구하고 락을 획득해 버리는" 것에 있으며, 우선순위의 유무와는 관계가 없으므로, 둘 다 문제를 직접적으로 해결하는 것은 아니다.[15] 스핀락이 콘보이 문제를 벗어나는 것에서 명백하듯이, "프로세스가 스스로 락을 획득하는" 구현으로 제한하는 것이 본질적인 해결책이 된다.[15]

참조

[1] 논문 Solution of a problem in concurrent programming control
[2] 간행물 The Black-White Bakery Algorithm http://www.cs.tau.ac[...] In Proc. Distributed Computing, 18th international conference, DISC 2004 2004
[3] 웹사이트 PODC Influential Paper Award: 2002 http://www.podc.org/[...] 2009-08-24
[4] 서적 Distributed computing: fundamentals, simulations, and advanced topics http://ca.wiley.com/[...] John Wiley & Sons, Inc. 2004-03-25
[5] 간행물 The Mutual Exclusion Problem Part II: Statement and Solutions http://research.micr[...] 2000-06-26
[6] 논문 A Pragmatic Implementation of Non-blocking Linked-lists https://timharris.uk[...] 2022-12-01
[7] 논문 A new solution of Dijkstra's concurrent programming problem 1974-08
[8] 논문 The Design of a Multicore Extension of the SPIN Model Checker https://pure.tue.nl/[...] 2007-10-01
[9] 간행물 Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable http://research.micr[...] 1982-01
[10] 간행물 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing 2016-07
[11] 간행물 Solution of a problem in concurrent programming control http://www.di.ens.fr[...] Communications of the ACM 1965-09
[12] 간행물 The Black-White Bakery Algorithm http://www.cs.tau.ac[...] In Proc. Distributed Computing, 18th international conference, DISC 2004 2004
[13] 간행물 A new solution of Dijkstra’s concurrent programming problem http://www.dc.uba.ar[...] Communications of the ACM 1974-08
[14] 논문 The Design of a Multicore Extension of the SPIN Model Checker http://ieeexplore.ie[...] IEEE Transactions on Software Engineering 2007-10
[15] 문서 優先度上限プロトコルは、ロックを獲得したいプロセスがすべて上限いっぱいの優先度であると機能しない。優先度継承は、ロック獲得中のプロセスよりも優先度が高いプロセスがロックを獲得しようとするまで動作しない。


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com